// https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/
// 有向无环图中一个节点的所有祖先
/**
 * - 节点 0 ，1 和 2 没有任何祖先。
- 节点 3 有 2 个祖先 0 和 1 。
- 节点 4 有 2 个祖先 0 和 2 。
- 节点 5 有 3 个祖先 0 ，1 和 3 。
- 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
- 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。
示例 2：



输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ，1 和 2 。
- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。
 */

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function (n, edges) {
    let ret = initRet(n);
    edges.forEach((edge) => {
        let [end, start] = edge;
        if (ret[start].includes(end)) {
            return;
        }
        ret[start].push(end);
    });

    for (let i = 0; i < n; i++) {
        let arr = [];
        ret[i] = findNodes(i, ret, arr);
        ret[i] = [...new Set(ret[i])].sort();
    }

    console.log(`ret: ${JSON.stringify([...Object.values(ret)])}`);
    return [...Object.values(ret)];
};

var findNodes = function (node, ret, arr) {
    if (ret[node].length === 0) {
        return arr;
    }

    arr = arr.concat(ret[node]);
    ret[node].forEach((item) => {
        arr = findNodes(item, ret, arr);
    });

    return arr;
};

var initRet = function (n) {
    let ret = {};
    for (let i = 0; i < n; i++) {
        ret[i] = [];
    }
    return ret;
};

getAncestors(5, [
    [0, 1],
    [0, 2],
    [0, 3],
    [0, 4],
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 3],
    [2, 4],
    [3, 4],
]); // [[],[0],[0,1],[0,1,2],[0,1,2,3]]

getAncestors(8, [
    [0, 3],
    [0, 4],
    [1, 3],
    [2, 4],
    [2, 7],
    [3, 5],
    [3, 6],
    [3, 7],
    [4, 6],
]); // [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
